Méthodes de Monte Carlo

6. Prédiction avec échantillonnage préférentiel (Importance Sampling)

6.2. Ratio d'échantillonage préférentiel

Quasiment toutes les stratégies de type Off-Policy utilisent l'échantillonnage préférentiel. C'est une technique qui permet d'estimer des valeurs dont les probabilités sont régies par une distribution spécifique à partir d'échantillons tirés d'une autre distribution. L'idée dans le cadre des stratégies de type Off-Policy et d'appliquer des coefficients aux valeurs obtenues à partir de l'analyse des trajectoires issues de la stratégie d'exploration (c'est-à-dire la stratégie comportementale) pour en déduire les valeurs liées à la stratégie à optimiser (c'est-à-dire la stratégie cible). Ce coefficient est appelé le ratio d'échantillonnage préférentiel.

Si on considère que l'agent se trouve dans un état $S_t$ à l'instant $t$, alors la probabilité de suivre la trajectoire à venir ($A_t, S_{t+1},A_{t+1},...,S_T$) en suivant la stratégie $\pi$ est donc:

$$\begin{array}{l} \Pr \left\{ {{A_t},{S_{t + 1}},{A_{t + 1}},...,{A_{T - 1}},{S_T}|{S_t},{A_{t - 1}} \sim \pi } \right\}\\ {\rm{ }} = \pi \left( {{A_t}|{S_t}} \right)p\left( {{S_{t + 1}}|{S_t},{A_t}} \right)\pi \left( {{A_{t + 1}}|{S_{t + 1}}} \right)p\left( {{S_{t + 2}}|{S_{t + 1}},{A_{t + 1}}} \right) \cdots \pi \left( {{A_{T - 1}}|{S_{T - 1}}} \right)p\left( {{S_T}|{S_{T - 1}},{A_{T - 1}}} \right)\\ {\rm{ }} = \prod\limits_{k = t}^{T - 1} {\pi \left( {{A_k}|{S_k}} \right)p\left( {{S_{k + 1}}|{S_k},{A_k}} \right)} \end{array}$$

On peut donc définir la probabilité relative de la trajectoire obtenue en suivant la stratégue cible $\pi$ par rapport à la trajectoire obtenue en suivant la stratégie comportementale $b$ (le ratio d'échantillonnage préférentiel) :

$${\rho _{t:T - 1}} = \frac{{\Pr \left\{ {{A_t},{S_{t + 1}},{A_{t + 1}},...,{A_{T - 1}},{S_T}|{S_t},{A_{t - 1}} \sim \pi } \right\}}}{{\Pr \left\{ {{A_t},{S_{t + 1}},{A_{t + 1}},...,{A_{T - 1}},{S_T}|{S_t},{A_{t - 1}} \sim b} \right\}}} = \frac{{\prod\limits_{k = t}^{T - 1} {\pi \left( {{A_k}|{S_k}} \right)p\left( {{S_{k + 1}}|{S_k},{A_k}} \right)} }}{{\prod\limits_{k = t}^{T - 1} {b\left( {{A_k}|{S_k}} \right)p\left( {{S_{k + 1}}|{S_k},{A_k}} \right)} }}$$

$${\rho _{t:T - 1}} = \frac{{\prod\limits_{k = t}^{T - 1} {\pi \left( {{A_k}|{S_k}} \right)} }}{{\prod\limits_{k = t}^{T - 1} {b\left( {{A_k}|{S_k}} \right)} }}$$

On voit que malgré le fait que les trajectoires dépendent des probabilités de transition du MDP, celles-ci n'apparaissent pas dans le calcul du ratio d'échantillonnage préférentiel. Ce ratio ne dépend que des stratégies utilisées et non du MDP.

Notre problématique est d'estimer l'espérance des revenus obtenus par l'agent en suivant la stratégie cible $\pi$, mais uniquement à partir des revenus $G_t$ obtenus en suivant la stratégie comportementale $b$. L'espérance de ces revenus nous permet d'obtenir la valeur de l'état $s$ en suivant la stratégie $b$ : $V_b(s) = {E_b}\left[ {{G_t}|{S_t} = s} \right]$. Mais nous souhaitons obtenir $V_\pi(s)$.

Pour cela, on fait intervenir le ratio d'échantillonnage préférentielle de la manière suivante:

$${V_\pi }\left( s \right) = {E_\pi }\left[ {{\rho _{t:T - 1}}{G_t}|{S_t} = s} \right]$$